package com.wmx.datastructuresandalgorithms.sortalgorithm;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

/**********************************
 * @author wmx
 * @date 2019/8/30 11:30
 * @description:
 * @version 1.0
 * 它的原理是每插入一个数都要将它和之前的已经完成排序的序列进行重新排序，也就是要找到新插入的数对应原序列中的位置。
 * 那么也就是说，每次插入一个数都要对原来排序好的那部分序列进行重新的排序，时间复杂度同样为O（n²）。
 * 这种算法是稳定的排序方法
 *
 * 在排序之前我们需要搞清一个思路,新插入一个数据的时候,排序过后的数组都是从小到大排列好的,所以我们需要从后往前查找,
 * 直到找到比我们要插入的数字还小的值。这个时候我们需要一个变量j作为标识
 *
 * 对于从小到大排序的时候：
 *
 * 当插入的数据比较小的数，后移的次数明显增多 。影响效率。
 *
 ************************************/
public class InsertionSort {

    public static void main(String[] args) {

        int [] arr = {299,100,444,20,99,1};
         insertionSort(arr);
        //创建100000条数据测试冒泡排序的时间
        /*int [] arr2 =new int[80000];
        for (int i = 0; i <80000; i++) {
            arr2[i] = (int)(Math.random()*800000);
        }*/
        //开始排序时间
       /* Date date = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:hh:ss");
        System.out.println("排序时的时间："+simpleDateFormat.format(date));

        insertionSort(arr2);

        Date date1 = new Date();
        System.out.println("排序时的时间："+simpleDateFormat.format(date1));*/

    }

    public static void insertionSort(int [] arr){
        for (int i = 1; i <arr.length ; i++) {
            int value = arr[i];
            int j ;
            for ( j= i-1; j >= 0; j--) {
                //将大于temp的数向后移动一步
                if(arr[j]>value){
                    arr[j+1] = arr[j];//记录j的值也就是temp要插入的位置
                }else{
                    break;
                }
            }
            arr[j+1] = value;
            System.out.println("第"+i+"趟排序"+Arrays.toString(arr));
        }
    }


    //插入排序，申明插入排序使用小到大排序。
    public static void insertionSort1(int [] arr){
        for (int i = 1; i <arr.length-1 ; i++) {
             int value = arr[i];
             int j ;
             for (j = i-1; j >=0 ; j--) {
                 if(arr[j]>value){
                     arr[j+1] = arr[j];
                 }else {
                     break;
                 }
            }
            arr[j+1] =value;
        }
    }


}
